package leetcode_700;

/**
 *@author 周杨
 *DesignCircularDeque_641 实现双向循环队列
 *describe:AC 62%
 *2018年9月25日 上午10:24:39
 */
public class DesignCircularDeque_641 {
	  private Integer[] queue;
	    int head = 0;
	    int tail = 0;
	    int n;

	    /**
	     * Initialize your data structure here. Set the size of the deque to be k.
	     */
	    public DesignCircularDeque_641(int k) {
	        queue = new Integer[k];
	        n = k;
	    }

	    /**
	     * Adds an item at the front of Deque. Return true if the operation is successful.
	     */
	    public boolean insertFront(int value) {
	        if (isFull()) {
	            return false;
	        } else if (!isEmpty()) {
	            head = modIndex(--head);
	        }
	        queue[head] = value;
	        return true;

	    }

	    /**
	     * Adds an item at the rear of Deque. Return true if the operation is successful.
	     */
	    public boolean insertLast(int value) {

	        if (isFull()) {
	            return false;
	        } else if (!isEmpty()) {
	            tail = modIndex(++tail);
	        }
	        queue[tail] = value;
	        return true;


	    }

	    /**
	     * Deletes an item from the front of Deque. Return true if the operation is successful.
	     */
	    public boolean deleteFront() {
	        if (isEmpty()) {
	            return false;
	        } else if (head == tail) {
	            queue[head] = null;
	        } else {
	            queue[head++] = null;
	            head = modIndex(head);
	        }
	        return true;
	    }

	    private int modIndex(int index) {
	        if (index < 0) {
	            index += n;
	        } else if (index >= n) {
	            index -= n;
	        }
	        return index;
	    }

	    /**
	     * Deletes an item from the rear of Deque. Return true if the operation is successful.
	     */
	    public boolean deleteLast() {
	        if (isEmpty()) {
	            return false;
	        } else if (head == tail) {
	            queue[tail] = null;
	        } else {
	            queue[tail--] = null;
	            tail = modIndex(tail);
	        }
	        return true;
	    }

	    /**
	     * Get the front item from the deque.
	     */
	    public int getFront() {

	        return isEmpty() ? -1 : queue[head];
	    }

	    /**
	     * Get the last item from the deque.
	     */
	    public int getRear() {

	        return isEmpty() ? -1 : queue[tail];
	    }

	    /**
	     * Checks whether the circular deque is empty or not.
	     */
	    public boolean isEmpty() {
	        return head == tail && queue[head] == null;
	    }

	    /**
	     * Checks whether the circular deque is full or not.
	     */
	    public boolean isFull() {
	        // if (head - tail == 1 || Math.abs(head - tail) == n - 1) {
	        return (head - tail == 1 || tail - head == n - 1);
	    }
}
